{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum Root to Leaf Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求根节点到叶节点数字之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个二叉树的根节点 <code>root</code> ，树中每个节点都存放有一个 <code>0</code> 到 <code>9</code> 之间的数字。\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>每条从根节点到叶节点的路径都代表一个数字：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，从根节点到叶节点的路径 <code>1 -> 2 -> 3</code> 表示数字 <code>123</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>计算从根节点到叶节点生成的 <strong>所有数字之和</strong> 。</p>\n",
    "\n",
    "<p><strong>叶节点</strong> 是指没有子节点的节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg\" style=\"width: 212px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3]\n",
    "<strong>输出：</strong>25\n",
    "<strong>解释：</strong>\n",
    "从根到叶子节点路径 <code>1->2</code> 代表数字 <code>12</code>\n",
    "从根到叶子节点路径 <code>1->3</code> 代表数字 <code>13</code>\n",
    "因此，数字总和 = 12 + 13 = <code>25</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg\" style=\"width: 292px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,9,0,5,1]\n",
    "<strong>输出：</strong>1026\n",
    "<strong>解释：</strong>\n",
    "从根到叶子节点路径 <code>4->9->5</code> 代表数字 495\n",
    "从根到叶子节点路径 <code>4->9->1</code> 代表数字 491\n",
    "从根到叶子节点路径 <code>4->0</code> 代表数字 40\n",
    "因此，数字总和 = 495 + 491 + 40 = <code>1026</code>\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 1000]</code> 内</li>\n",
    "\t<li><code>0 <= Node.val <= 9</code></li>\n",
    "\t<li>树的深度不超过 <code>10</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-root-to-leaf-numbers](https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-root-to-leaf-numbers](https://leetcode.cn/problems/sum-root-to-leaf-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[4,9,0,5,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def helper(node,sum):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            \n",
    "            if not node.left and not node.right:\n",
    "                sum = sum*10 + node.val\n",
    "                return sum\n",
    "            \n",
    "            sum = sum * 10 +node.val\n",
    "            \n",
    "            return helper(node.left,sum)+helper(node.right,sum)\n",
    "        \n",
    "        return helper(root,0)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = 0\n",
    "    def sumNumbers(self, root: 'TreeNode') -> 'int':\n",
    "        '''\n",
    "        深度优先遍历，递归执行每一条路径上的数字计算求和\n",
    "        '''\n",
    "        if root == None:\n",
    "            return 0\n",
    "        if root.left:\n",
    "            root.left.val += 10 * root.val\n",
    "        if root.right:\n",
    "            root.right.val += 10 * root.val\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            self.result += root.val\n",
    "        self.sumNumbers(root.left)\n",
    "        self.sumNumbers(root.right)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def dfs(res,cur,n):\n",
    "            if not n:\n",
    "                return res\n",
    "            if not n.left and not n.right:\n",
    "                return res + cur * 10 + n.val\n",
    "            res = dfs(res, cur * 10 + n.val, n.left)\n",
    "            return dfs(res, cur * 10 + n.val, n.right)\n",
    "        return dfs(0, 0, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Author : lining\n",
    "# 2019/1/7 21:43\n",
    "# Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.\n",
    "#\n",
    "# An example is the root-to-leaf path 1->2->3 which represents the number 123.\n",
    "#\n",
    "# Find the total sum of all root-to-leaf numbers.\n",
    "#\n",
    "# Note: A leaf is a node with no children.\n",
    "#\n",
    "# Example:\n",
    "#\n",
    "# Input: [1,2,3]\n",
    "#     1\n",
    "#    / \\\n",
    "#   2   3\n",
    "# Output: 25\n",
    "# Explanation:\n",
    "# The root-to-leaf path 1->2 represents the number 12.\n",
    "# The root-to-leaf path 1->3 represents the number 13.\n",
    "# Therefore, sum = 12 + 13 = 25.\n",
    "#\n",
    "# Example 2:\n",
    "#\n",
    "# Input: [4,9,0,5,1]\n",
    "#     4\n",
    "#    / \\\n",
    "#   9   0\n",
    "#  / \\\n",
    "# 5   1\n",
    "# Output: 1026\n",
    "# Explanation:\n",
    "# The root-to-leaf path 4->9->5 represents the number 495.\n",
    "# The root-to-leaf path 4->9->1 represents the number 491.\n",
    "# The root-to-leaf path 4->0 represents the number 40.\n",
    "# Therefore, sum = 495 + 491 + 40 = 1026.\n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.sum = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        for x in self.bl(root, 0):\n",
    "            print(x)\n",
    "            self.sum += x\n",
    "        return self.sum \n",
    "        \n",
    "\n",
    "    def bl(self, node, upperval):\n",
    "        if node.left is None and node.right is None:\n",
    "            yield node.val + upperval *10\n",
    "        if node.left:\n",
    "            yield from self.bl(node.left,upperval*10 +node.val)\n",
    "        if node.right:\n",
    "            yield from self.bl(node.right, upperval * 10 + node.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        res=self.dfs(root)\n",
    "        resstr=[[str(i) for i in res[j]] for j in range(len(res))]\n",
    "        resnum=[int(''.join(i)) for i in resstr]\n",
    "        return sum(resnum)\n",
    "        \n",
    "    def dfs(self,root):\n",
    "        if not root:\n",
    "            return None\n",
    "        if not root.left and not root.right:\n",
    "            return [[root.val]]\n",
    "        res=[]\n",
    "        if root.left:\n",
    "            lstleft=self.dfs(root.left)\n",
    "            for i in range(len(lstleft)):\n",
    "                res.append([root.val]+lstleft[i])\n",
    "        if root.right:\n",
    "            lstright=self.dfs(root.right)\n",
    "            for j in range(len(lstright)):\n",
    "                res.append([root.val]+lstright[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root):\n",
    "        res=[]\n",
    "        self.check(res,root,0)\n",
    "        return sum(res)\n",
    "        \n",
    "    \n",
    "    def check(self,res,root,acc):\n",
    "        if not root:\n",
    "            return\n",
    "        acc = acc*10+root.val\n",
    "        if not root.left and not root.right:\n",
    "            res.append(acc)\n",
    "\n",
    "        self.check(res,root.left,acc)\n",
    "        self.check(res,root.right,acc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root :\n",
    "            return 0\n",
    "        res = self.dfs(root,0)\n",
    "        return res\n",
    "\n",
    "    def dfs(self,root,sum):\n",
    "        if not root :\n",
    "            return 0\n",
    "        sum = sum*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            return sum\n",
    "        return self.dfs(root.left,sum)+self.dfs(root.right,sum) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # res = 0\n",
    "        # level = [(root,root.val)]\n",
    "        # while level:\n",
    "        #     for i in range(len(level)):\n",
    "        #         node,val_ = level.pop(0)\n",
    "        #         if node.left:\n",
    "        #             level.append((node.left,val_*10+node.left.val))\n",
    "        #         if node.right:\n",
    "        #             level.append((node.right,val_*10+node.right.val))        \n",
    "        #         if not node.left and not node.right:\n",
    "        #             res+=val_\n",
    "        # return res\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "#         if not root:\n",
    "#             return 0\n",
    "#         res = 0\n",
    "#         queue = collections.deque([[root,root.val]])\n",
    "#         while queue:\n",
    "#             node,val = queue.popleft()\n",
    "            \n",
    "#             if not node.left and not node.right:\n",
    "#                 res+=val\n",
    "#             if node.left :\n",
    "#                 queue.append([node.left, node.left.val+10*val])\n",
    "#             if node.right :\n",
    "#                 queue.append([node.right, node.right.val+10*val])\n",
    "#         return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        stack = [(root,str(root.val))]\n",
    "        while stack:\n",
    "            node, num = stack.pop()\n",
    "            if node.right == None and node.left == None:\n",
    "                self.res += int(num)\n",
    "                continue\n",
    "            if node.left:\n",
    "                stack.append((node.left,num + str(node.left.val)))\n",
    "            if node.right:\n",
    "                stack.append((node.right,num + str(node.right.val)))\n",
    "\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [(root,root.val)]\n",
    "        total = 0\n",
    "        while stack:\n",
    "            node,num = stack.pop()\n",
    "            if not node.left and not node.right:\n",
    "                total += num\n",
    "            if node.left:\n",
    "                stack.append((node.left,num*10+node.left.val))\n",
    "            if node.right:\n",
    "                stack.append((node.right,num*10+node.right.val))\n",
    "        \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.error = 0\n",
    "        self.res = 0\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            self.error = 1\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return root.val\n",
    "        res = [0]\n",
    "        self.helper(root, 0, res)\n",
    "        return res[0]\n",
    "    def helper(self, root, now, res):\n",
    "        if not root:\n",
    "            return []\n",
    "        elif not root.left and not root.right:\n",
    "            res[0] += now*10 + root.val\n",
    "            return [root.val]\n",
    "        self.helper(root.left,now*10+root.val,res)\n",
    "        self.helper(root.right,now*10+root.val,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def sumNumbers(self, root: TreeNode) -> int:\n",
    "#         if not root: return 0\n",
    "#         self.res = []\n",
    "#         self.dfs(root, [])\n",
    "#         res = 0\n",
    "#         # print(self.res)\n",
    "#         for i in range(len(self.res)):\n",
    "#             res += int(\"\".join(map(str, self.res[i])))\n",
    "#         return res \n",
    "\n",
    "#     def dfs(self, root, level):\n",
    "#         if not root.left and not root.right:\n",
    "#             self.res.append(level+[root.val])\n",
    "#             return \n",
    "#         if root.left:\n",
    "#             self.dfs(root.left, level + [root.val])\n",
    "#         if root.right:\n",
    "#             self.dfs(root.right, level + [root.val])\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def helper(root, tmp):\n",
    "            nonlocal res \n",
    "            if not root: return \n",
    "            if not root.left and not root.right:\n",
    "                res += int(tmp+str(root.val))\n",
    "                return \n",
    "            helper(root.left, tmp+str(root.val))\n",
    "            helper(root.right, tmp+str(root.val))\n",
    "        helper(root, \"\")\n",
    "        return res\n",
    "        \n",
    "# class Solution:\n",
    "#     def sumNumbers(self, root: TreeNode) -> int:\n",
    "#         self.res = 0\n",
    "#         self.dfs(root, [])\n",
    "#         return self.res \n",
    "#     def dfs(self, root, level):\n",
    "#         if not root: return \n",
    "#         if not root.left and not root.right:\n",
    "#             self.res += int(\"\".join(map(str, level+[root.val])))\n",
    "#         if root.left:\n",
    "#             self.dfs(root.left, level + [root.val])\n",
    "#         if root.right:\n",
    "#             self.dfs(root.right, level + [root.val])\n",
    "\n",
    "# class Solution:\n",
    "#     def sumNumbers(self, root: TreeNode) -> int:\n",
    "#         if not root: return 0\n",
    "#         res = 0\n",
    "#         q = collections.deque([(root, 0)])\n",
    "#         while q:\n",
    "#             for i in range(len(q)):\n",
    "#                 node, val = q.popleft()\n",
    "#                 if not node.left and not node.right:\n",
    "#                     res += val*10 + node.val \n",
    "#                 if node.left:\n",
    "#                     q.append((node.left, val*10+node.val ))\n",
    "#                 if node.right:\n",
    "#                     q.append((node.right, val*10+node.val))\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:return 0 \n",
    "        bfs = deque()\n",
    "        bfs.append(root)\n",
    "        result = 0\n",
    "        while bfs:\n",
    "            counts = len(bfs)\n",
    "            for i in range(counts):\n",
    "                temp = bfs.popleft()\n",
    "                if not temp.left and not temp.right:\n",
    "                    result += temp.val\n",
    "                if temp.left:\n",
    "                    temp.left.val += temp.val*10\n",
    "                    bfs.append(temp.left)\n",
    "                if temp.right:\n",
    "                    temp.right.val += temp.val*10\n",
    "                    bfs.append(temp.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preOrder(self, root, data, answer):\n",
    "        if root:\n",
    "            data.append(str(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                answer.append(int(''.join(data))) \n",
    "            \n",
    "            self.preOrder(root.left, data, answer)\n",
    "            self.preOrder(root.right, data, answer)\n",
    "            data.pop()\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        data = []\n",
    "        answer = []\n",
    "        self.preOrder(root, data, answer)\n",
    "        return sum(answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def helper(root , i):\n",
    "            if root == None:\n",
    "                return 0;\n",
    "            temp = i * 10 + root.val\n",
    "            if root.left == None and root.right == None:\n",
    "                return temp\n",
    "            return helper(root.left , temp) + helper(root.right , temp)\n",
    "        return helper(root , 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        # dfs\n",
    "        stack = []\n",
    "        if not root:\n",
    "            return 0\n",
    "        tmp = ''\n",
    "        stack.append((tmp, root))\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp, node = stack.pop()\n",
    "            if not node.left and not node.right:\n",
    "                res.append(tmp + str(node.val))\n",
    "            if node.right:\n",
    "                stack.append((tmp + str(node.val) ,node.right))\n",
    "            if node.left:\n",
    "                stack.append((tmp + str(node.val) ,node.left))\n",
    "        return sum([int(i) for i in res])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root,tmp_list,res_list):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.right is None and root.left is None:\n",
    "                tmp_list.append(root.val)\n",
    "\n",
    "                res_list.append(tmp_list[:])\n",
    "            else:\n",
    "                tmp_list.append(root.val)\n",
    "                if root.left:\n",
    "                    dfs(root.left,tmp_list,res_list)\n",
    "                    tmp_list.pop()\n",
    "\n",
    "                if root.right:\n",
    "                    dfs(root.right,tmp_list,res_list)\n",
    "                    tmp_list.pop()\n",
    "\n",
    "        tmp_list,res_list = [],[]\n",
    "        dfs(root,tmp_list,res_list)\n",
    "        res_list = [[str(y) for y in x] for x in res_list]\n",
    "\n",
    "\n",
    "        return sum(int(''.join(x)) for x in res_list)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def sumNumbers(self, root: TreeNode) -> int:    \n",
    "        if root is None:\n",
    "            return 0\n",
    "        @lru_cache(None)\n",
    "        def find_paths(root):  # 求当前root下所有的路径组成的列表paths\n",
    "            if root.left is None and root.right is None:\n",
    "                return ['']\n",
    "            paths = []\n",
    "            if root.left is not None:\n",
    "                paths.extend([str(root.left.val) + path_str for path_str in find_paths(root.left)])\n",
    "            if root.right is not None:\n",
    "                paths.extend([str(root.right.val) + path_str for path_str in find_paths(root.right)])\n",
    "            return paths\n",
    "        paths_list = [str(root.val) + path_str for path_str in find_paths(root)]\n",
    "        return sum(map(int, paths_list))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.dfs(root, num=0)\n",
    "        \n",
    "    def dfs(self, root, num):\n",
    "        if not root:\n",
    "            return 0\n",
    "        num = num*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            return num\n",
    "        return self.dfs(root.left, num) + self.dfs(root.right, num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode], base=0) -> int:\n",
    "        if root.left and root.right:\n",
    "            return self.sumNumbers(root.left, base*10+root.val) + self.sumNumbers(root.right, base*10+root.val)\n",
    "        elif root.left:\n",
    "            return self.sumNumbers(root.left, base*10+root.val)\n",
    "        elif root.right:\n",
    "            return self.sumNumbers(root.right, base*10+root.val)\n",
    "        else:\n",
    "            return base*10+root.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root,preval):\n",
    "            if not root:return 0\n",
    "            tmp = preval*10+root.val\n",
    "            if not root.right and not root.left:\n",
    "                return tmp\n",
    "            return dfs(root.left,tmp) + dfs(root.right,tmp)\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0 \n",
    "        def dfs(cur, root):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                dfs(10*cur + root.val, root.left)\n",
    "            if root.right:\n",
    "                dfs(10*cur + root.val, root.right)\n",
    "            if not root.left and not root.right:\n",
    "                ans += 10*cur + root.val\n",
    "        dfs(0, root)\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = []\n",
    "        def dfs(rt,num):\n",
    "            if rt is None:\n",
    "                return \n",
    "            if rt.left is None and rt.right is None:\n",
    "                ans.append(num+str(rt.val))\n",
    "                return\n",
    "            dfs(rt.left,num+str(rt.val))\n",
    "            dfs(rt.right,num+str(rt.val))\n",
    "        dfs(root,\"\")\n",
    "        return sum(map(int,ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        # 深度优先搜索\n",
    "        paths = []\n",
    "        def _traverse(path):\n",
    "            node = path[-1]\n",
    "            if not node.left and not node.right:\n",
    "                paths.append(path)\n",
    "                return \n",
    "            if node.left:\n",
    "                temp_path = deepcopy(path)\n",
    "                temp_path.append(node.left)\n",
    "                _traverse(temp_path)\n",
    "            if node.right:\n",
    "                temp_path = deepcopy(path)\n",
    "                temp_path.append(node.right)\n",
    "                _traverse(temp_path)\n",
    "\n",
    "        _traverse([root])\n",
    "        res = 0 \n",
    "        for path in paths:\n",
    "            temp = 0 \n",
    "            for i in range(len(path)):\n",
    "                temp += path[i].val * math.pow(10, (len(path) - i - 1))\n",
    "            res += temp \n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sum = 0\n",
    "        num = 0\n",
    "        self.dfs(root, num)\n",
    "        return self.sum\n",
    "\n",
    "    def dfs(self, root, num):\n",
    "        if not root.left and not root.right:\n",
    "            self.sum += num * 10 + root.val\n",
    "        else:\n",
    "            num = num * 10 + root.val\n",
    "            if root.left:\n",
    "                self.dfs(root.left, num)\n",
    "            if root.right:\n",
    "                self.dfs(root.right, num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        \n",
    "        def dfs(root, cur):\n",
    "            if not root:\n",
    "                res.append(int(cur))\n",
    "                return\n",
    "            cur += str(root.val)\n",
    "            if root.left:\n",
    "                dfs(root.left, cur)\n",
    "            if root.right:\n",
    "                dfs(root.right, cur)\n",
    "            if (not root.left) and (not root.right):\n",
    "                res.append(int(cur))\n",
    "                return\n",
    "\n",
    "        dfs(root, '')\n",
    "\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        nums = []\n",
    "\n",
    "        def dfs(node, tmp):\n",
    "            if not node.left and not node.right:\n",
    "                nums.append(tmp)\n",
    "                return\n",
    "            \n",
    "            if node.left:\n",
    "                dfs(node.left, tmp + [node.left.val])\n",
    "            if node.right:\n",
    "                dfs(node.right, tmp + [node.right.val])\n",
    "        \n",
    "        res = 0\n",
    "        dfs(root, [root.val])\n",
    "        for num in nums:\n",
    "            s = ''\n",
    "            for i in num:\n",
    "                s += str(i)\n",
    "            res += int(s)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
